Cyclic redundancy code (CRC) has been used for a long time to preserve the integrity of digital data in storage and transmission systems. More particularly, CRC is an important error detection tool used for communications and data processing applications. The CRC schemes are often used for checking integrity of data because they are easy to implement and they detect a large class of errors. CRC is a kind of checksum which is transmitted with data between a source node and a target node over a communications medium. The source node calculates the CRC for the data to be transferred using a predetermined polynomial and then transmits the data along with the CRC to the target node where the CRC of the received data is independently generated using the predetermined generator polynomial and compared with the CRC received from the source node to check if errors have occurred during the transmission. Treating the data or message as a binary polynomial, its CRC corresponding to a particular generator polynomial may be generated by raising the message polynomial to a proper power first and then taking the remainder of the message polynomial divided by the generator polynomial. For CRC generation, data bits are typically serially inputted into a CRC generator in order to produce the appropriate CRC code for transmission along with the data. Traditionally, CRC codes are generated with Linear Feedback Shift Register (LFSR) circuits. An LFSR takes the input data and shifts through a series of flip-flops on successive clock cycles. Combinations of the shift register output and data input are fed back to the flip-flops via exclusive-OR gates. An LFSR can be defined in terms of a generator polynomial which relates the input data and the CRC code via a polynomial expression and of which “+” is an exclusive-OR operation. The state of the flip-flops upon completion of the shifting process is the CRC code.
For example, ATM uses a FCS field derived from CRC error detection codes for error checking. The integrity of the transmitted or processed message in an ATM system is ensured by the addition at the end of the message of the FCS traveling with the message itself so it can be checked on the reception side for proper transmission. The FCS code has been standardized for data integrity checking as described in the ANSI X3.139-1987 document pages 28 and 29. All the CRC codes constitute a finite Galois Field (GF), and the CRC32 codes belong to the GF generated by the following generator polynomial of degree 32:g(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1This generator polynomial of degree 32 was chosen as a standard for error checking in Ethernet and then chosen by the ATM standard for AAL5 error checking. In the circuitry for calculating the FCS or checking the message, an LFSR carries out a bit by bit multiplication in the GF, i.e., modulo the polynomial on which GF is generated, and by which each bit of the message is inputted into the LFSR in the manner of most significant bit (MSB) first and division is performed by feedbacks. At the end of the process, the FCS, i.e., the remainder of the division, is within the shift registers.
Hardware implementation for CRC generators in large scale digital systems is preferred because it is faster. The drawback of hardware implementation of CRCs is that more hardware is required with consequent increase in cost, size and complexity and a decrease in reliability. Software implemented CRCs are known although their use is not widespread because of the speed penalty thought to be inevitable. Those skilled in the art understand that choosing a polynomial of a larger degree will result in greater error detection. However, for the applications of current large scale systems, the desired hardware becomes too complicated and costly to be implemented and the required software needs huge computations. Several improvements were made for CRC generators. For example, by using CRC routines to generate tables consisting of all possible combinations of the chosen polynomial, the checksum generation is reduced to a table lookup. These CRC routines are considered to be the fastest software implementations available, but they take up a great deal of dedicated memory. Early CRC implementations use the concept of LFSR in which the polynomial division is processed one bit at a time. However, the serial processing for the generation of the CRC is relatively slow, and as the technology advanced, single-bit CRC generation was not enough to handle high-speed data processing and transmission, and parallel CRC algorithms were then developed to meet this need. The key reason that existing CRC algorithms are limited in their degree of parallelism is deeply rooted in the concept of LFSRs. All existing algorithms try to solve the same problem, i.e., how to parallelize the bit-by-bit operation of LFSRs. As a result, the degree of parallelism never goes beyond the perceived size of LFSRs.
Accordingly, it is desired a parallelized CRC calculation method and system to reduce the processing for generation of CRC codes.